Field of the Invention
The present invention generally relates to a fault-localization and error-correction method for a self-checking binary signed-digit adder and a digital logic circuit for performing the method. More particularly, the present invention relates to a fault-localization and error-correction method for a self-checking binary signed-digit adder, by which a stuck-at fault of the self-checking binary signed-digit adder may be detected at low cost and with low complexity and by which an error may be autonomously corrected using a self-dual concept, and to a digital logic circuit for performing the method.
Description of the Related Art
In an arithmetic operation, signed-digit representation aims to eliminate the propagation of carries.
In the Binary Signed-Digit Number (BSDN) system proposed by Cardarilli et al, the binary signed-digit number ‘a’ may be represented as the following Equation (1):
                    a        =                              ∑                          i              =              1                                      n              -              1                                ⁢                                          ⁢                                    x              i                        ⁢                          2              i                                                          (        1        )            
where xi∈{−1,0,1}, and n denotes the number of digits.
First, in order to calculate the addition of signed-digit numbers, it is necessary to calculate an intermediate sum and an intermediate carry. Here, the intermediate sum and the intermediate carry are calculated using the computation rule shown in FIG. 1, and this may be represented using the following Equation (2):ai+bi=2ti+1+wi  (2)where a denotes an addend, b denotes an augend, t denotes an intermediate carry, and w denotes an intermediate sum.
Also, referring to FIG. 1, when a pair comprising the addend ai and the augend bi is (0, 0), (−1, −1), (1, 1) or (−1, 1), the intermediate carry and the intermediate sum are calculated as (0, 0), (−1, 0), (1, 0), or (0, 0), respectively, without using the number of a previous digit position (i −1).
However, under the condition in which a pair comprising the addend ai and the augend bi is (−1, 0), if the sum of the addend ai−1 and the augend bi−1 at a previous digit position is less than ‘0’, the intermediate carry and the intermediate sum become (−1, 1), but if not, they become (0, −1). Also, under the condition in which a pair comprising the addend ai and the augend bi is (1, 0), if the sum of the addend ai−1 and the augend bi−1 at the previous digit position is greater than ‘0’, the intermediate carry and the intermediate sum become (1, −1), but if not, they become (0, 1).
Meanwhile, Cardarilli et al. proposed a self-checking binary signed-digit adder using a parity checker in order to detect a stuck-at fault.
FIG. 2 shows Cardarilli's self-checking binary signed-digit adder. This adder 10 includes an adder unit 11 for outputting a result ‘z’ by adding an addend ‘a’ and an augend ‘b’ and an error indicator unit 12 for detecting a computational error of the adder unit 11.
Also, the adder unit 11 includes multiple first adders ADD1s for calculating the addition of an addend ai and an augend bi using an intermediate carry ti and an intermediate sum wi based on the computation rule shown in FIG. 1, and multiple second adders ADD2s arranged so as to correspond to respective first adders ADD1s. Here, each of the second adders serves to output a final result by adding the intermediate sum wi from the corresponding first adder and the intermediate carry ti−1 from the first adder, having calculated the value of the previous digit.
Also, the error indicator unit 12 includes a parity predictor 12a for predicting parity by receiving an addend and an augend, a first XOR gate 12b for outputting the parity of a result of an XOR operation that is performed on the parity of the addend and the parity of the augend, a first error indicator 12c for receiving the output of the first XOR gate 12b and the intermediate sums of the first adders ADD1s and for detecting an error by performing an XOR operation on the received values, a second XOR gate 12d for receiving the output values of the second adders ADD2s and outputting the parity of a result of an XOR operation performed on the received values, and a second error indicator 12f for receiving the parity output from the parity predictor 12a, the parity output from the first XOR gate 12b, and the parity output from the second XOR gate 12d and for detecting an error by performing an XOR operation on the received values.
Meanwhile, according to the method proposed by Cardarilli et al., when an error is detected in the error indicator unit 12, the bits of the initially input addend and augend are shifted to the left and right, and recomputation is performed on the shifted input. Then, the result of the initial computation is compared with the result of the recomputation, whereby a stuck-at fault is detected. However, this method is disadvantageous in that cost and complexity are increased in the detection of the stuck-at fault and error correction.